package dynamicProgramming;

/**
 * 应该分持有/不持有两种情况, 然后迭代一下, 每个时间点的状态只依赖于上一个时间点。
 */
public class P0714买卖股票的最佳时机含手续费 {




    /**
     * 超时
     * 状态转移为, 以当前点为结尾的最大收益, 这个结尾, 可能是在当前点抛出, 也可能是在之前抛出, 然后直到当前点也不买入。
     * 这个状态数组一定是单调的
     */
    public int maxProfit(int[] prices, int fee) {
        int[] maxGain = new int[prices.length + 1];// 多一个, 0之前的收益是0
        for(int i = 2; i <= prices.length; i++){
            maxGain[i] = maxGain[i - 1];
            if(prices[i - 1] < prices[i - 2]) continue;
            for(int j = 1; j < i; j++){
                maxGain[i] = Math.max(maxGain[i], maxGain[j - 1] + prices[i - 1] - prices[j - 1] - fee);
            }
        }
        //System.out.println(Arrays.toString(maxGain));
        int result = -1;
        for(int i : maxGain) result = Math.max(i, result);
        return result;
    }
}
